package com.gxc.string;

import java.util.*;

/**
 * 每个数字关联多个字母，关联关系如下：
 *
 * 0 关联 “a”,”b”,”c”
 * 1 关联 “d”,”e”,”f”
 * 2 关联 “g”,”h”,”i”
 * 3 关联 “j”,”k”,”l”
 * 4 关联 “m”,”n”,”o”
 * 5 关联 “p”,”q”,”r”
 * 6 关联 “s”,”t”
 * 7 关联 “u”,”v”
 * 8 关联 “w”,”x”
 * 9 关联 “y”,”z”
 * 输入一串数字后，通过数字和字母的对应关系可以得到多个字母字符串（要求按照数字的顺序组合字母字符串）；
 *
 * 屏蔽字符串：屏蔽字符串中的所有字母不能同时在输出的字符串出现，如屏蔽字符串是abc，则要求字符串中不能同时出现a,b,c，但是允许同时出现a,b或a,c或b,c等；
 *
 * 给定一个数字字符串和一个屏蔽字符串，输出所有可能的字符组合；
 *
 * 例如输入数字字符串78和屏蔽字符串ux，输出结果为uw，vw，vx；数字字符串78，可以得到如下字符串uw，ux，vw，vx；由于ux是屏蔽字符串，因此排除ux，最终的输出是uw，vw，vx;
 *
 * 输入描述
 * 第一行输入为一串数字字符串，数字字符串中的数字不允许重复，数字字符串的长度大于0，小于等于5；
 *
 * 第二行输入是屏蔽字符串，屏蔽字符串的长度一定小于数字字符串的长度，屏蔽字符串中字符不会重复；
 *
 * 输出描述
 * 输出可能的字符串组合
 *
 * 注：字符串之间使用逗号隔开，最后一个字符串后携带逗号
 */
public class NumberString {

    static List<String> map = Arrays.asList("abc", "def", "ghi", "jkl", "mno", "pqr", "st", "uv", "wx", "yz");
    static Set<Character> filterSet = new HashSet<>();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String digits = scanner.nextLine();
        String filter = scanner.nextLine();
        scanner.close();

        // 记录需要筛选的字符
        for (char c : filter.toCharArray()) {
            filterSet.add(c);
        }

        // 获取对应的字母映射
        List<String> letters = new ArrayList<>();
        for (char c : digits.toCharArray()) {
            letters.add(map.get(c - '0'));
        }

        StringBuilder res = new StringBuilder();
        dfs(letters, 0, new StringBuilder(), res, new HashSet<>());

        // 输出结果
        System.out.println(res.toString());
    }

    // 递归回溯
    static void dfs(List<String> letters, int index, StringBuilder path, StringBuilder res, Set<Character> used) {
        if (index == letters.size()) {
            if (isContainsAllFilterChars(used)) {
                res.append(path).append(",");
            }
            return;
        }

        // 遍历当前数字对应的字母
        for (char c : letters.get(index).toCharArray()) {
            path.append(c);
            used.add(c);
            dfs(letters, index + 1, path, res, used);
            path.deleteCharAt(path.length() - 1);
            used.remove(c);
        }
    }

    // 判断是否包含所有过滤字符
    static boolean isContainsAllFilterChars(Set<Character> used) {
        for (char x : filterSet) {
            if (!used.contains(x)) {
                return true;
            }
        }
        return false;
    }
}
